package ikelib;


/*
	FFT.java
	Fast Fourier Transform
*/

public class FFT {

	// Main Routine
	public static void execute(boolean inverse, Field[] f) {
		int n = f.length;
		int n2 = n >> 1;
		Field[] wtbl = f[0].make_wtbl(n);

		for(int i=0, j=0;;) {
			if(i < j) { Field t = f[i]; f[i] = f[j]; f[j] = t;}
			if (++i >= n) break;
			int k = n2;
			while (k <= j) { j -= k; k >>= 1; }
			j += k;
		}

		Field t = f[0].copy();

		for(int k=1; k<n;) {
			int h = 0, k2 = k << 1, d = n / k2;
			for(int j=0; j<k; j++) {
				if(inverse)
					for(int i=j; i<n; i+=k2) {
						int ik = i + k;
						f[ik].timesBy(wtbl[h]);
						t.set(f[ik]).addTo(f[i]);
						f[ik].negate().addTo(f[i]);
						f[i].set(t);
					}
				else
					for(int i=j; i<n; i+=k2) {
						int ik = i + k;
						f[ik].timesBy(wtbl[n2-h]);
						t.set(f[ik]).negate().addTo(f[i]);
						f[ik].addTo(f[i]);
						f[i].set(t);
					}
				h += d;
			}
			k = k2;
		}
		if(! inverse)
			for(int i=0; i<n; i++) f[i].div(n);
	}

}
